package com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.algorithms.mst;

import com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.Edge;
import com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.Graph;
import com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.Vertex;
import com.liuzhilong.infrastructure.framework.algorithms.datastruct.line.IndexPriorityQueue;
import lombok.Setter;
import lombok.experimental.Accessors;

import java.util.*;
import java.util.stream.Collectors;

/**
 * <h1>Prim即时版本</h1>
 * <p>在延时版本{@link LasyPrimMST} 中，优先级队列中会保存很多失效的边，这样对于大图来说可能会有比较大的内存开销，并且对于优先级队列来说，数据量大也会影响上浮下沉的性能</p>
 * <h2>过程</h2>
 * <p>
 *     针对一个图来说，当一个新的顶点加入到最小生成树的时候，对于新顶点连接的顶点来说，距离最小生成树的距离可能会变近了。<br>
 *     即时版本的思想就从这个原理出发，每次更新顶点的时候，遍历这个顶底的边，更新边的另一个顶点距离树的权重。每次都从队列中获取权重最小的，往复循环到队列中没有数据。<br>
 *     相对与{@link LasyPrimMST} 这个方法的优势在于空间消耗要小。
 * </p>
 *
 */
public class PrimMST<T> {
    @Setter
    @Accessors(chain = true)
    private Graph<T> graph;
    //链接定点的边
    private Map<Vertex<T>, Edge<T>> map;
    //到边的最近的权重
    private Map<Vertex<T>, Double> recentlyWeight;
    //定点的优先级队列
    private IndexPriorityQueue<Vertex<T>, Double> indexPriorityQueue;

    //是否已经标记过
    Set<Vertex<T>> mark;

    public Iterable<Edge<T>> mst(){
        return map.entrySet().stream().map(Map.Entry::getValue).collect(Collectors.toList());
    }




    private PrimMST<T> init(){
        //初始化 设置所有的定点权重都是无穷
        this.graph.getVertices().entrySet().forEach(entity->{
            recentlyWeight.put(entity.getValue(), Double.MAX_VALUE);
        });
        //寻找任意一个定点作为开始，进行验证
        this.graph.getVertices().entrySet().stream().map(Map.Entry::getValue).findAny().ifPresent(first->{
            recentlyWeight.put(first, 0.0d);
            indexPriorityQueue.insert(first,0.0d);
        });

        while(!indexPriorityQueue.isEmpty()){
            visit(indexPriorityQueue.pull().getKey());
        }
        return this;
    }

    /**
     * 标记某个顶点，并把顶点中的列放在优先队列中。
     * @param vertex
     */
    private void visit(Vertex<T> vertex){
        //标记
        mark.add(vertex);
        //遍历顶点
        vertex.getNext().forEach(edge->{

            Vertex<T> other = edge.other(vertex);
            //在mst中的忽略掉
            if (mark.contains(other)) {
                return;
            }
            //如果之前保存的权重小于这个edge的权重，不进行任何操作。否则进行进行权重的计算。

            if(edge.getWeight()<this.recentlyWeight.get(other)){
                recentlyWeight.put(other, edge.getWeight());
                if(indexPriorityQueue.contains(other)){
                    indexPriorityQueue.change(other,edge.getWeight());
                }else {
                    indexPriorityQueue.insert(other,edge.getWeight());
                }
                this.map.put(other, edge);
            }

        });

    }


    private PrimMST(Graph<T> graph){
        this.graph = graph;
        this.map = new HashMap<>(graph.getVertices().keySet().size());
        this.indexPriorityQueue = new IndexPriorityQueue<>(graph.getVertices().keySet().size(), true);
        mark = new HashSet<>(graph.getVertices().keySet().size());
        this.recentlyWeight = new HashMap<>(graph.getVertices().keySet().size());

    }

    public static <T> PrimMST<T> create(Graph<T> graph){
        return new PrimMST<>(graph).init();
    }

}
